#include<iostream>
using namespace std;

/*
问题描述：
       八皇后问题
*/

void print(bool array[][4] ,int count) {
    cout << "***********  "<<" 第 "<<count<<" 种解"<<"  ******************"<<endl;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cout << array[i][j] << " ";
        }
        cout << endl;
    }
}

bool noDanger(bool array[][4], int row, int column) {
    if (0 == row) return true;  //第 0 行直接放置成功

    int i = row - 1, j = column;    //判断当前列是否存在皇后
    for (i; i >= 0; i--) {
        if (array[i][j] == true) return false;
    }

    i = row - 1; j = column - 1;
    for (; i >= 0 && j >= 0; i--, j--) {    //判断左上斜对角线是否存在皇后
        if (array[i][j] == true) return false;
    }

    i = row - 1; j = column + 1;
    for (; i >= 0 && j < 4; i--, j++) { //判断右上斜对角线是否存在皇后
        if (array[i][j] == true) return false;
    }

    return true;
}

void eightQueens(bool array[][4] ,int row, int &count) {
    
    for (int j = 0; j < 4; j++) {   //遍历每一列
        array[row][j] = true;       //在当前位置 放置皇后
        if (noDanger(array, row, j)) {  //判断皇后是否冲突
            if (3 == row) {         //若已放置到最后一行，输出当前的一个解
                count++;
                print(array,count);
            }
            else
            {
                eightQueens(array, row + 1,count);  //若未放置到最后一行，继续往下一行寻找
            }

        }
        array[row][j] = false;  
    }
}


int main() {
    bool array[4][4];       //维护一个二维矩阵 ，true代表该位置有皇后，false代表无
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            array[i][j] = false;        //初始化为 false
        }
    }
    int count = 0;  //解的总数
    eightQueens(array, 0,count);
    return 0;
}

// 时间复杂度分析：
// 解释：数据规模不影响递归调用次数,与贪心一致。
// 所以最好时间复杂度=最坏时间复杂度=平均时间复杂度=O（1）
// 空间复杂度分析：
// 没有开辟新的内存空间，所以最好空间复杂度=最坏空间复杂度=平均空间复杂度=O（1）
// 解释：递归过程并没有新空间的创建，所以空间复杂度为O（1）
